#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

struct Bottle
{
	int min;
	int max;
};

struct MyLess
{
	int remain;
	bool operator()(const Bottle& lhs, const Bottle& rhs)
	{
		return remain % lhs.min - remain / lhs.min * (lhs.max - lhs.min) < remain % rhs.min - remain / rhs.min * (rhs.max - rhs.min);
	}
};

int main()
{
	int amount, count;
	while (scanf("%d %d", &amount, &count) != EOF)
	{
		amount *= 1000;
		vector<Bottle> bottles;
		while (count--)
		{
			Bottle bottle;
			scanf("%d %d", &bottle.min, &bottle.max);
			bottles.push_back(bottle);
		}
		int flexibility = 0;
		while (1)
		{
			MyLess less;
			less.remain = amount;
			nth_element(bottles.begin(), bottles.begin(), bottles.end(), less);
			
			Bottle b = bottles[0];
			if (b.min < amount)
			{
				flexibility += amount / b.min * (b.max - b.min);
				amount %= b.min;
			}
			else
			{
				break;
			}
		}
		
		int remain = amount - flexibility;
		if (remain < 0)
			remain = 0;
		printf("%d\n", remain);
	}
	return 0;
}